package leetcode.weekly.week299;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

//Solution4Test
public class Solution6 {
	int[] nums;

	public int minimumScore(int[] nums, int[][] edges) {
		this.nums = nums;
		int n = nums.length;
		List<Integer>[] nexts = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			nexts[i] = new ArrayList<>();
		}
		for (int i = 0; i < edges.length; i++) {
			int[] cur = edges[i];
			int a = cur[0], b = cur[1];
			nexts[a].add(b);
			nexts[b].add(a);
		}
		int[] parents = new int[n];
		List<Integer>[] children = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			children[i] = new ArrayList<>();
		}
		boolean[][] uppers = new boolean[n][n];
		int[] xors = new int[n];
		boolean[] upper = new boolean[n];
		relationship(0, -1, parents, children, nexts, xors, upper, uppers);
		int ans = Integer.MAX_VALUE;
		for (int i = 0; i < edges.length; i++) {
			for (int j = i + 1; j < edges.length; j++) {
				int[] del1 = edges[i], del2 = edges[j];
				int a = del1[0], b = del1[1];
				int c = del2[0], d = del2[1];
				int val1 = 0, val2 = 0, val3 = 0;
				if (a == c || a == d || b == c || b == d) {
					int[] vals = this.val2(a, b, c, d, xors, children, uppers);
					val1 = vals[0];
					val2 = vals[1];
					val3 = vals[2];
				} else {
					int[] vals = this.val(a, b, c, d, xors, children, uppers);
					val1 = vals[0];
					val2 = vals[1];
					val3 = vals[2];
				}
				int max = Math.max(val1, Math.max(val3, val2));
				int min = Math.min(val1, Math.min(val3, val2));
				ans = Math.min(ans, max - min);
			}
		}
		return ans;
	}

	private int[] val2(int a, int b, int c, int d, int[] xors, List<Integer>[] children, boolean[][] uppers) {
		int p1 = -1, p2 = -1, p3 = -1;
		if (a == c) {
			p1 = b;
			p2 = d;
			p3 = a;
		}
		if (a == d) {
			p1 = b;
			p2 = c;
			p3 = a;
		}
		if (b == c) {
			p1 = a;
			p2 = d;
			p3 = b;
		}
		if (b == d) {
			p1 = a;
			p2 = c;
			p3 = b;
		}
		if (children[p3].contains(p1) && children[p3].contains(p2)) {
			return new int[] { xors[p1], xors[p2], xors[0] ^ xors[p1] ^ xors[p2] };
		}
		if (uppers[p1][p2])
			return new int[] { xors[p3] ^ xors[p1], xors[p1], xors[0] ^ xors[p3] };
		else
			return new int[] { xors[p3] ^ xors[p2], xors[p2], xors[0] ^ xors[p3] };
	}

	// 2 ,4
	private int[] ret1(int b, int d, int[] xors) {
		return new int[] { xors[b] ^ xors[d], xors[d], xors[0] ^ xors[b] };
	}

	private int[] ret2(int b, int d, int[] xors) {
		return new int[] { xors[b], xors[d], xors[0] ^ xors[b] ^ xors[d] };
	}

	private int[] ret3(int b, int d, int[] xors) {
		return new int[] { xors[b], xors[d], xors[0] ^ xors[b] ^ xors[d] };
	}

	private int[] ret(int a, int b, int c, int d, int[] xors, boolean[][] uppers) {
		if (uppers[c][b]) {
			// a b c d
			return this.ret1(b, d, xors);
		}
		if (uppers[c][a]) {
			// a b , a c d
			return this.ret2(b, d, xors);
		}
		// c d a b
		if (uppers[a][d]) {
			return this.ret1(d, b, xors);
		}
		// c d ,c a b
		if (uppers[a][c]) {
			return this.ret2(d, b, xors);
		}
		// a b , c d
		return this.ret3(b, d, xors);
	}

	private int[] val(int a, int b, int c, int d, int[] xors, List<Integer>[] children, boolean[][] uppers) {
		if (children[a].contains(b) && children[c].contains(d)) {
			// ab + cd
			return this.ret(a, b, c, d, xors, uppers);
		} else if (children[a].contains(b) && children[d].contains(c)) {
			// ab + dc
			return this.ret(a, b, d, c, xors, uppers);
		} else if (children[b].contains(a) && children[c].contains(d)) {
			// ba + cd
			return this.ret(b, a, c, d, xors, uppers);
		} else if (children[b].contains(a) && children[d].contains(c)) {
			// ba + dc
			return this.ret(b, a, d, c, xors, uppers);
		} else {
			return null;
		}
	}

	private int relationship(int me, int parent, int[] parents, List<Integer>[] children, List<Integer>[] nexts,
			int[] xors, boolean[] upper, boolean[][] uppers) {
		parents[me] = parent;
		List<Integer> myNext = nexts[me];
		int xor = this.nums[me];
		uppers[me] = Arrays.copyOf(upper, upper.length);
		upper[me] = true;
		for (int next : myNext) {
			if (next != parent) {
				xor ^= this.relationship(next, me, parents, children, nexts, xors, upper, uppers);
				children[me].add(next);
			}
		}
		upper[me] = false;
		xors[me] = xor;
		return xor;
	}
}
